{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Delete Operation for Two Strings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minDistance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #两个字符串的删除操作"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个单词&nbsp;<code>word1</code>&nbsp;和<meta charset=\"UTF-8\" />&nbsp;<code>word2</code>&nbsp;，返回使得<meta charset=\"UTF-8\" />&nbsp;<code>word1</code>&nbsp;和&nbsp;<meta charset=\"UTF-8\" />&nbsp;<code>word2</code><em>&nbsp;</em><strong>相同</strong>所需的<strong>最小步数</strong>。</p>\n",
    "\n",
    "<p><strong>每步&nbsp;</strong>可以删除任意一个字符串中的一个字符。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> word1 = \"sea\", word2 = \"eat\"\n",
    "<strong>输出:</strong> 2\n",
    "<strong>解释:</strong> 第一步将 \"sea\" 变为 \"ea\" ，第二步将 \"eat \"变为 \"ea\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 &nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>word1 = \"leetcode\", word2 = \"etco\"\n",
    "<b>输出：</b>4\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "<meta charset=\"UTF-8\" />\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= word1.length, word2.length &lt;= 500</code></li>\n",
    "\t<li><code>word1</code>&nbsp;和&nbsp;<code>word2</code>&nbsp;只包含小写英文字母</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [delete-operation-for-two-strings](https://leetcode.cn/problems/delete-operation-for-two-strings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [delete-operation-for-two-strings](https://leetcode.cn/problems/delete-operation-for-two-strings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"sea\"\\n\"eat\"', '\"leetcode\"\\n\"etco\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        houses.sort()\n",
    "        n = len(houses)\n",
    "        \n",
    "        def helper(i, j):\n",
    "            mid = (i + j) // 2\n",
    "            res = 0\n",
    "            for x in range(i, j+1):\n",
    "                res += abs(houses[x] - houses[mid])\n",
    "            return res\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, k):\n",
    "            if idx == n:\n",
    "                return 0\n",
    "            if k == 1:\n",
    "                return helper(idx, n - 1)\n",
    "            \n",
    "            ans = float('inf')\n",
    "            for x in range(idx, n):\n",
    "                tmp = helper(idx, x) + dfs(x+1, k-1)\n",
    "                ans = min(ans, tmp)\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        houses.sort()\n",
    "        h = [0 for _ in range(len(houses) + 1)]\n",
    "        for i in range(1, len(houses) + 1):\n",
    "            h[i] = houses[i - 1]\n",
    "\n",
    "        pre_sum = [0 for _ in range(len(houses) + 1)]\n",
    "        pre_sum[0] = 0\n",
    "        for i in range(1, len(houses) + 1):\n",
    "            pre_sum[i] = pre_sum[i - 1] + houses[i - 1]\n",
    "\n",
    "\n",
    "        def f(l, r):\n",
    "            if (r + l) % 2 == 0:\n",
    "                mid = int((r + l) / 2)\n",
    "            else:\n",
    "                mid = int((r + l - 1) / 2)\n",
    "            res = pre_sum[l - 1] + pre_sum[r] - 2 * pre_sum[mid]\n",
    "            if (r + l) % 2 == 0:\n",
    "                res += h[mid]\n",
    "            return res\n",
    "\n",
    "        dp = [[0 for _ in range(len(houses) + 1)] for _ in range(k + 1)]\n",
    "        houses.sort()\n",
    "        dp[1][0] = 0\n",
    "        for i in range(1, len(houses) + 1):\n",
    "            dp[1][i] = f(1, i)\n",
    "        for i in range(2, k + 1):\n",
    "            for j in range(0, len(houses) + 1):\n",
    "                dp[i][j] = math.inf\n",
    "        for i in range(2, k + 1):\n",
    "            for j in range(1, len(houses) + 1):\n",
    "                for p in range(0, j):\n",
    "                    dp[i][j] = min(dp[i][j], dp[i - 1][p] + f(p + 1, j))\n",
    "\n",
    "        return dp[k][len(houses)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        def dis(houses, i, j):\n",
    "            n = i - j\n",
    "            d = 0\n",
    "            for k in range(n//2):\n",
    "                d += houses[i-k] - houses[j+k+1]\n",
    "            return d \n",
    "        dp = [[float('inf')]*k for _ in range(len(houses))]\n",
    "        houses.sort()\n",
    "\n",
    "        for i in range(len(houses)):\n",
    "            dp[i][0] = dis(houses, i, -1)\n",
    "\n",
    "        for k_ in range(1, k):\n",
    "            for i in range(k_, len(houses)):\n",
    "                d = float('inf')\n",
    "                for j in range(i):\n",
    "                    d = min(d, dis(houses, i, j) + dp[j][k_-1])\n",
    "                dp[i][k_] = d \n",
    "        return dp[-1][k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        houses.sort() #预排序处理\n",
    "        n=len(houses) #房子的总数\n",
    "        mindist=[[0 for j in range(n)] for i in range(n)]    #mindist[i][j]记录从下标为i的房子到下标为j的房子，只用一个邮筒所能达到的最小距离和\n",
    "        for i in range(n):\n",
    "            for j in range(i,n):\n",
    "                mid=(i+j)//2   #整除取中位数\n",
    "                for p in range(i,j+1):\n",
    "                    mindist[i][j]=mindist[i][j]+abs(houses[p]-houses[mid])\n",
    "        dp=[[float('inf') for j in range(n)] for i in range(k)]   #dp[i][j]表示i+1个邮筒，第1到第j+1个房子的最优方案对应的最小距离和\n",
    "        for j in range(n):\n",
    "            dp[0][j]=mindist[0][j]\n",
    "        for i in range(1,k):\n",
    "            for j in range(n):\n",
    "                for p in range(i-1,j):\n",
    "                    dp[i][j]=min(dp[i][j],dp[i-1][p]+mindist[p+1][j])\n",
    "        return dp[k-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        if k>= len(houses): return 0\n",
    "        houses.sort()\n",
    "\n",
    "        def getdistance(n,start):\n",
    "            if n==1: return 0\n",
    "            elif n==2: return abs(houses[start]-houses[start+1])\n",
    "            else:\n",
    "                times=n//2\n",
    "                ans=0\n",
    "                for i in range(times):\n",
    "                    ans+=abs(houses[start+i]-houses[start+n-1-i])\n",
    "                return ans\n",
    "\n",
    "        from functools import lru_cache\n",
    "        @lru_cache(None)\n",
    "        def dp(h,k,start):\n",
    "            if h<=k: return 0\n",
    "            if k==1: return getdistance(h,start)\n",
    "            ans=float(\"inf\")\n",
    "            for i in range(1,h-k+2):\n",
    "                ans=min(ans,getdistance(i,start)+dp(h-i,k-1,start+i))\n",
    "            return ans\n",
    "\n",
    "        return dp(len(houses),k,0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        n = len(houses)\n",
    "        houses.sort()\n",
    "        f = [[inf] * n for _ in range(k)]\n",
    "        def dst(l, r):\n",
    "            res = 0\n",
    "            while l < r:\n",
    "                res += abs(houses[l] - houses[r])\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            return res\n",
    "        for i in  range(n):\n",
    "            f[0][i] = dst(0, i)\n",
    "        for i in range(1, k):\n",
    "            for j in range(i, n - (k-i-1)):\n",
    "                for m in range(i-1, j):\n",
    "                    f[i][j] = min(f[i][j], f[i-1][m] + dst(m+1, j))\n",
    "        return f[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        houses.sort()\n",
    "        n = len(houses)\n",
    "        cost = [[0] * n for _ in range(n)]\n",
    "        for l in range(n - 2, -1, -1):\n",
    "            for r in range(l + 1, n):\n",
    "                cost[l][r] = cost[l + 1][r - 1] + houses[r] - houses[l]\n",
    "        f = [[inf] * (k + 1) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            # 前i个房子一个邮箱的情况\n",
    "            f[i][1] = cost[0][i]\n",
    "            # 枚举邮箱个数\n",
    "            for j in range(2, min(k, i + 1) + 1):\n",
    "                # 枚举上一个邮箱的所管辖的位置的右端点\n",
    "                for i0 in range(i):\n",
    "                    if f[i0][j - 1] != inf:\n",
    "                        f[i][j] = min(f[i][j], f[i0][j - 1] + cost[i0 + 1][i])\n",
    "        return f[n - 1][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        houses.sort()\n",
    "        n = len(houses)\n",
    "        cost = [[0] * n for _ in range(n)]\n",
    "        for l in range(n - 2, -1, -1):\n",
    "            for r in range(l + 1, n):\n",
    "                cost[l][r] = cost[l + 1][r - 1] + houses[r] - houses[l]\n",
    "        f = [[inf] * (k + 1) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            f[i][1] = cost[0][i]\n",
    "            for j in range(2, min(k, i + 1) + 1):\n",
    "                for i0 in range(i):\n",
    "                    if f[i0][j - 1] != inf:\n",
    "                        f[i][j] = min(f[i][j], f[i0][j - 1] + cost[i0 + 1][i])\n",
    "        return f[n - 1][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        inf = 10**9\n",
    "        n = len(houses)\n",
    "        houses.sort()\n",
    "        dp = [[inf for _ in range(k+1)] for _ in range(n+1)]\n",
    "        for i in range(0, k+1):\n",
    "            dp[i][i] = 0\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, min(k+1, i+1)):\n",
    "                for x in range(j-1, i):\n",
    "                    cost = 0\n",
    "                    l = x+1\n",
    "                    r = i\n",
    "                    while l <= r:\n",
    "                        # print(i, j, l, r, houses)\n",
    "                        cost += houses[r-1] - houses[l-1]\n",
    "                        l += 1\n",
    "                        r -= 1\n",
    "                    dp[i][j] = min(dp[i][j], dp[x][j-1] + cost)\n",
    "                    # print(i,j, dp[i][j], x, j-1, cost)\n",
    "        # print(dp)\n",
    "        return dp[n][k]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, nums: List[int], K: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        cost = [[0] * n for _ in range(n)]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                cost[i][j] = cost[i + 1][j - 1] + nums[j] - nums[i]\n",
    "        f = [[inf] * (K + 1) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            f[i][1] = cost[0][i]\n",
    "            for j in range(2, min(i + 1, K) + 1):\n",
    "                for u in range(i):\n",
    "                    f[i][j] = min(f[i][j], f[u][j - 1] + cost[u + 1][i])\n",
    "        return f[n - 1][K]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        n = len(houses)\n",
    "\n",
    "        houses.sort()\n",
    "\n",
    "        @cache\n",
    "        def dp(idx, t):\n",
    "            if t == 0 and idx == n:\n",
    "                return 0\n",
    "            elif t == 0:\n",
    "                return inf\n",
    "            elif idx == n:\n",
    "                return inf\n",
    "\n",
    "            ret = inf\n",
    "\n",
    "            for i in range(idx + 1, n + 2 - t):\n",
    "                d = sum(abs(houses[j] - houses[(i + idx) // 2]) for j in range(idx, i))\n",
    "\n",
    "                ret = min(ret, d + dp(i, t - 1))\n",
    "\n",
    "            return ret\n",
    "\n",
    "        return dp(0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        houses.sort()#排序\n",
    "        pre = [0]#前缀和\n",
    "        l = len(houses)\n",
    "        for i in range(l):\n",
    "            pre.append(pre[-1] + houses[i])\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, k):#分别是房屋下标和剩余邮筒数量\n",
    "            if l - i <= k:#如果邮筒数量大于等于房子数量，那么距离和一定为0\n",
    "                return 0\n",
    "            elif k == 1:#如果邮筒数量为1\n",
    "                j = (l + i) // 2#中位数\n",
    "                return houses[j] * (j - i) - (pre[j] - pre[i]) + pre[l] - pre[j] - houses[j] * (l - j)#中位数 * 左区间大小 - 左区间和 + 右区间和 - 中位数 * 右区间大小\n",
    "            res = dfs(i + 1, k - 1)#当前邮筒只覆盖一个房子\n",
    "            for n in range(i + 1, l):#覆盖多个房子\n",
    "                j = (n + 1 + i) // 2#中位数\n",
    "                res = min(res, houses[j] * (j - i) - (pre[j] - pre[i]) + pre[n + 1] - pre[j] - houses[j] * (n + 1 - j) + dfs(n + 1, k - 1))#中位数 * 左区间大小 - 左区间和 + 右区间和 - 中位数 * 右区间大小 + 继续深搜的结果\n",
    "            return res\n",
    "        return dfs(0, k)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "     def minDistance(self, houses: List[int], k: int) -> int:\n",
    "       houses.sort()\n",
    "       n = len(houses)\n",
    "       @cache\n",
    "       def dfs(i: int, j: int) -> int:\n",
    "          if i == n :\n",
    "             return 0\n",
    "          if j == k :\n",
    "             return inf\n",
    "          res = inf\n",
    "          for x in range(i, n) :\n",
    "             res = min(res, dfs(x + 1, j + 1) + dis(i, x))\n",
    "          return res\n",
    "       def dis(i: int , j: int) -> int:\n",
    "          res = 0\n",
    "          while i < j:\n",
    "            res += houses[j] - houses[i]\n",
    "            j -= 1\n",
    "            i += 1\n",
    "          return res\n",
    "       return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int: \n",
    "        Len = len(houses)\n",
    "        houses.sort()\n",
    "        @cache \n",
    "        def get_dis(i, j):\n",
    "            if i == j:\n",
    "                return 0\n",
    "            elif j == i+1:\n",
    "                return houses[j-1] - houses[i-1]\n",
    "            else:\n",
    "                return get_dis(i+1, j-1) + houses[j-1] - houses[i-1]\n",
    "\n",
    "\n",
    "\n",
    "        @cache \n",
    "        def f(n, k): # 前n个房子， k 个邮箱\n",
    "            if k == 1:\n",
    "                return get_dis(1, n)\n",
    "            t = inf \n",
    "            for i in range(k-1, n):\n",
    "                t = min(t, f(i, k-1) + get_dis(i+1, n))\n",
    "            return t \n",
    "        return f(Len, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        def dis(l, r):\n",
    "            mid = (l + r) >> 1\n",
    "            return sum(houses[mid + 1: r + 1]) - sum(houses[l:mid + 1]) + houses[mid] * abs((mid - l + 1) - (r - mid))\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == len(houses):\n",
    "                return 0 if j == 0 else inf\n",
    "            return min(dfs(t + 1, j - 1) + dis(i, t) for t in range(i, len(houses)))\n",
    "\n",
    "        houses.sort()\n",
    "        return dfs(0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        houses.sort()\n",
    "        n = len(houses)\n",
    "        # 预处理，获得[i,j]区域内放置一个桶的最小距离,将一个桶放置到屋子中位时距离将最小\n",
    "        cost = [[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                # 遍历[i,j]的房子，房子位置-[i,j]中位距离和为[i,j]放置一个桶的最小距离\n",
    "                for curK in range(i, j+1):\n",
    "                    cost[i][j] += abs(houses[curK] - houses[(i+j)//2])\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i, curK):\n",
    "            if i == n: # 遍历到末尾，没有值\n",
    "                return float(\"inf\")\n",
    "            if curK == 1: # 只剩下一个桶，直接安放\n",
    "                return cost[i][n-1]\n",
    "            ans = float(\"inf\")\n",
    "            for j in range(i, n):\n",
    "                ans = min(ans, cost[i][j] + dfs(j+1, curK-1))\n",
    "            return ans\n",
    "        return dfs(0, k)\n",
    "    def minDistance2(self, houses: List[int], k: int) -> int:\n",
    "        houses.sort()\n",
    "        n = len(houses)\n",
    "        right = max(houses)\n",
    "        def getCost(stationNums):\n",
    "            cost = 0\n",
    "            ns = len(stationNums)\n",
    "            for h in houses:\n",
    "                postIdx = bisect.bisect_left(stationNums, h)\n",
    "                if postIdx == 0:\n",
    "                    cost += abs(stationNums[0] - h)\n",
    "                elif postIdx == ns:\n",
    "                    cost += abs(stationNums[-1] - h)\n",
    "                else:\n",
    "                    cost += min(abs(stationNums[postIdx-1] - h), abs(stationNums[postIdx] - h))\n",
    "            return cost\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i, curK, stationNums):\n",
    "            if curK == 0:\n",
    "                return getCost(stationNums)\n",
    "            ans = float(\"inf\")\n",
    "            for postStation in range(i, right+1):\n",
    "                ans = min(ans, dfs(postStation, curK - 1, stationNums + tuple([postStation])))\n",
    "            return ans\n",
    "        return dfs(0, k, tuple([]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        houses.sort()\n",
    "        @cache\n",
    "        def f(i,j,box_nums):\n",
    "            if box_nums>=j-i:return 0\n",
    "            if box_nums==1:\n",
    "                # if (j-i)%2==1: \n",
    "                mid=houses[(i+j)//2]\n",
    "                # else :mid=houses[(i+j)//2]\n",
    "                dis=sum(\n",
    "                    [abs(mid-houses[k]) for k in range(i,j,1)]\n",
    "                )\n",
    "                return dis\n",
    "            else:\n",
    "                ret=min(\n",
    "                    [f(i,k,box_nums-1)+f(k,j,1) for k in range(i+1,j,1)]\n",
    "                )\n",
    "                return ret\n",
    "        return f(0,len(houses),k)\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def minDistance(self, h: List[int], k: int) -> int:\n",
    "#         h.sort()\n",
    "#         @cache \n",
    "#         def f(i,j,k): #houses[i,j)之间安排k个邮筒\n",
    "#             if j - i <= k:  return 0\n",
    "#             if k == 1 : return h[j-1]-h[i] + f(i+1,j-1,k)\n",
    "#             return min(\n",
    "#                 f(i,m,k-1) + f(m,j,1) for m in range(i+k-1,j)\n",
    "#             )\n",
    "#         return f(0,len(h),k)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        n = len(houses)\n",
    "        houses.sort()\n",
    "        cost = [[0] * n for _ in range(n)]\n",
    "        \n",
    "        @cache\n",
    "        def cal(i, j):\n",
    "            if i >= j: return 0\n",
    "            cost[i][j] = cal(i + 1, j - 1) + houses[j] - houses[i]\n",
    "            return cost[i][j]\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                cal(i, j)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if j == 1: return cost[0][i]\n",
    "            res = inf\n",
    "            for i0 in range(j - 2, i):\n",
    "                if j >= 2: res = min(res, dfs(i0, j - 1) + cost[i0 + 1][i])\n",
    "            return res\n",
    "        return dfs(n - 1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        houses.sort()\n",
    "        n = len(houses)\n",
    "        # houses[i:j]放置k个邮筒\n",
    "        @cache\n",
    "        def f(i, j, k):\n",
    "            if j-i+1 < k:\n",
    "                return 0\n",
    "            if k == 1:\n",
    "                return houses[j]-houses[i]+f(i+1, j-1, 1)\n",
    "            return min(f(i, mid, k-1)+f(mid+1, j, 1) for mid in range(i, j))\n",
    "        return f(0, n-1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, h: List[int], k: int) -> int:\n",
    "        h.sort()\n",
    "        n = len(h)\n",
    "        @cache\n",
    "        def f(i, j, k):\n",
    "            if i==j:\n",
    "                if k>=0:\n",
    "                    return 0 \n",
    "                return float('inf')\n",
    "            else:\n",
    "                if k==1:\n",
    "                    d = (j-i)//2 \n",
    "                    tmp = (h[i+d] + h[j-d])/2 \n",
    "                    ans = 0 \n",
    "                    for ix in range(i, j+1):\n",
    "                        ans += abs(tmp - h[ix])\n",
    "                    return  ans \n",
    "                else:\n",
    "                    ans = float('inf')\n",
    "                    for ix in range(i+1, j+1):\n",
    "                        ans = min(ans, f(i, ix-1, k-1) + f(ix, j, 1))\n",
    "                    return ans \n",
    "        return int(f(0, n-1, k))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], K: int) -> int:\n",
    "        n = len(houses)\n",
    "        houses.sort()\n",
    "        @cache\n",
    "        def dfs(l,r,k):\n",
    "            if l>=r:\n",
    "                return 0\n",
    "\n",
    "            if k == 1:\n",
    "                return houses[r] - houses[l] + dfs(l+1,r-1,1)\n",
    "\n",
    "            ans = inf\n",
    "            for j in range(l,r):\n",
    "                ans = min(ans, dfs(l,j,1)+dfs(j+1,r,k-1))\n",
    "            return ans\n",
    "        return dfs(0,n-1,K)\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        \n",
    "        n = len(houses)\n",
    "        @lru_cache(None)\n",
    "        def dfs(i,j,k):\n",
    "            if i >= j:return 0\n",
    "            if k == 1:\n",
    "                return houses[j] - houses[i] + dfs(i+1,j-1,1)\n",
    "            ans = inf\n",
    "            for l in range(i,j+1):\n",
    "                ans = min(ans,dfs(i,l,1) + dfs(l+1,j,k-1))\n",
    "            return ans\n",
    "        houses.sort()\n",
    "        return dfs(0,len(houses)-1,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        from functools import lru_cache\n",
    "        n = len(houses)\n",
    "        houses.sort()\n",
    "\n",
    "        # when house i to house j share one mailbox, the optimal allocation is the median house position.\n",
    "        @lru_cache(n * (n + 1) // 2)\n",
    "        def one_mailbox_min_dist(i: int, j: int) -> int:\n",
    "            ret = 0\n",
    "            while i < j:\n",
    "                ret += houses[j] - houses[i]\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            return ret\n",
    "\n",
    "        # minimum distance for first i + 1 houses with j + 1 mailboxes\n",
    "        @lru_cache(n * k)\n",
    "        def min_dist(i: int, j: int) -> int:\n",
    "            if j == 0:\n",
    "                return one_mailbox_min_dist(0, i)\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            # last one mailbox for i - r houses\n",
    "            return min(min_dist(r, j - 1) + one_mailbox_min_dist(r + 1, i) for r in range(i))\n",
    "\n",
    "        return min_dist(n - 1, k - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import gc; gc.disable()\n",
    "ndp = [0]*101\n",
    "dp = [0]*101\n",
    "class Solution:\n",
    "    def minDistance(self, A: List[int], k: int) -> int:\n",
    "        n = len(A)\n",
    "        A.sort()\n",
    "        pre = list(accumulate(A, initial=0))\n",
    "        @cache\n",
    "        def onegroup(l, r):\n",
    "            m1 = (r+l-1)//2\n",
    "            m2 = (r+l)//2\n",
    "            return pre[r] - pre[m2] - pre[m1+1] + pre[l]\n",
    "        \n",
    "        # vk = 1\n",
    "        for sz in range(0, n+1): dp[sz] = onegroup(0, sz)\n",
    "        \n",
    "        def dc(sz_l, sz_r, p_l, p_r):\n",
    "            \"\"\" both closed interval \"\"\"\n",
    "            if sz_l > sz_r: return\n",
    "            sz_m = (sz_l+sz_r+1)//2\n",
    "            p, p_cost = p_l, dp[p_l] + onegroup(p_l, sz_m)\n",
    "            for can_p in range(p_l+1, p_r+1):\n",
    "                if (can_p_cost := dp[can_p] + onegroup(can_p, sz_m)) < p_cost: \n",
    "                    p, p_cost = can_p, can_p_cost\n",
    "\n",
    "            ndp[sz_m] = p_cost\n",
    "            dc(sz_l, sz_m-1, p_l, p)\n",
    "            dc(sz_m+1, sz_r, p, p_r)\n",
    "        \n",
    "        for vk in range(2, k+1):\n",
    "            dc(vk, n, 0, n)\n",
    "            for i in range(0, n+1): dp[i] = ndp[i]\n",
    "\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        houses.sort()\n",
    "        dist = [[[0 for i in range(k + 1)] for i in range(len(houses))] for i in range(len(houses))]\n",
    "        for i in range(len(houses)):\n",
    "            for j in range(i, len(houses)):\n",
    "                if i == j:\n",
    "                    dist[i][j][1] = 0\n",
    "                elif i == j - 1:\n",
    "                    dist[i][j][1] = houses[j] - houses[i]\n",
    "                else:\n",
    "                    dist[i][j][1] = self.calculate_distance(houses[i:j+1], houses[i + (j - i) // 2])\n",
    "        for kk in range(2, k):\n",
    "            for i in range(len(houses)):\n",
    "                for j in range(i + kk - 1, len(houses)):\n",
    "                    min_dist = -1\n",
    "                    for pivot in range(i + kk - 1, j + 1):\n",
    "                        if min_dist == -1 or min_dist > dist[i][pivot - 1][kk-1] + dist[pivot][j][1]:\n",
    "                            min_dist = dist[i][pivot - 1][kk-1] + dist[pivot][j][1]\n",
    "                    dist[i][j][kk] = min_dist\n",
    "        if k > 1:\n",
    "            min_dist = -1\n",
    "            for pivot in range(k - 1, len(houses)):\n",
    "                if min_dist == -1 or min_dist > dist[0][pivot - 1][k-1] + dist[pivot][len(houses) - 1][1]:\n",
    "                    min_dist = dist[0][pivot - 1][k-1] + dist[pivot][len(houses) - 1][1]\n",
    "            dist[0][len(houses) - 1][k] = min_dist\n",
    "        return dist[0][len(houses) - 1][k]\n",
    "\n",
    "    def calculate_distance(self, houses: List[int], post_box : int) -> int:\n",
    "        dist = 0\n",
    "        for house in houses:\n",
    "            dist += abs(house - post_box)\n",
    "        return dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        houses.sort()\n",
    "        dp = [[[0 for i in range(len(houses))] for j in range(len(houses))] for t in range(k)]\n",
    "        for number1 in range(k):\n",
    "            if number1 == 0:\n",
    "                for i in range(len(houses)):\n",
    "                    for j in range(i,len(houses)):\n",
    "                        if i == j:\n",
    "                            dp[number1][i][j] = 0\n",
    "                        else:\n",
    "                            size1 = i\n",
    "                            size2 = j\n",
    "                            while size2 > size1:\n",
    "                                dp[number1][i][j] += houses[size2] - houses[size1]\n",
    "                                size1 += 1\n",
    "                                size2 -= 1\n",
    "            else:\n",
    "                rig = len(houses)-(k-number1-1)\n",
    "                for  rig1 in range(number1,rig):\n",
    "                    for i in range(rig1-number1+1):\n",
    "                        if dp[number1][0][rig1] == 0:\n",
    "                            dp[number1][0][rig1] = dp[number1-1][0][rig1-i-1] + dp[0][rig1-i][rig1]\n",
    "                        else:\n",
    "                            dp[number1][0][rig1] = min(dp[number1-1][0][rig1-i-1] + dp[0][rig1-i][rig1],dp[number1][0][rig1])\n",
    "        return dp[-1][0][len(houses)-1]\n",
    "                \n",
    "\n",
    "                                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int: \n",
    "        if len(houses)<=k:\n",
    "            return 0 \n",
    "        houses.sort()\n",
    "        n = len(houses)\n",
    "        inf = 100*10000+1\n",
    "        # 3-dim dp:\n",
    "        # 100 x 100 x 100\n",
    "        # 在前 i 个房子中，放置了 j 个邮筒， 最后一个邮筒的位置是第 l 个房子\n",
    "        answer = [[[inf]*n for _ in range(k)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(k):\n",
    "                for l in range(j,i+1): \n",
    "                    if j>=i and l==i:\n",
    "                        answer[i][j][l] = 0\n",
    "                        continue\n",
    "                    if j==0:\n",
    "                        # 只有一个邮筒，它放在了第l个房子的位置 \n",
    "                        answer[i][j][l] = sum([abs(x-houses[l])for x in houses[:i+1]] )\n",
    "                    elif l<i:\n",
    "                        # 最后一个邮筒，并不放在最后一个房子的位置\n",
    "                        answer[i][j][l] = answer[l][j][l] + sum([abs(x-houses[l])for x in houses[l+1:i+1]] )\n",
    "                    else:\n",
    "                        # 有多个邮筒，它们放在不同的位置\n",
    "                        # 开始检索倒数第二个邮筒所有可能的位置\n",
    "                        tt = inf\n",
    "                        for ll in reversed(range(j-1,l)): \n",
    "                            t = answer[ll][j-1][ll] + sum([min(abs(x-houses[ll]),abs(x-houses[l]))for x in houses[ll+1:i+1]] )\n",
    "                            tt = min(t,tt)\n",
    "                        answer[i][j][l] = tt\n",
    "        xx = answer[n-1][k-1]\n",
    "        return min(xx)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        if len(houses) <= k:\n",
    "            return 0 \n",
    "        houses.sort()\n",
    "        n = len(houses)\n",
    "        # 3-dim dp:\n",
    "        # 100 x 100 x 100\n",
    "        # 在前 i 个房子中，放置了 j 个邮筒， 最后一个邮筒的位置是第 l 个房子\n",
    "        dp = [[[float('+inf')] * n for _ in range(k)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(k):\n",
    "                for l in range(j,i+1): \n",
    "                    if j >= i and l == i:\n",
    "                        dp[i][j][l] = 0\n",
    "                        continue\n",
    "                    if j == 0:\n",
    "                        # 只有一个邮筒，它放在了第l个房子的位置 \n",
    "                        dp[i][j][l] = sum([abs(x-houses[l])for x in houses[:i+1]] )\n",
    "                    elif l < i:\n",
    "                        # 最后一个邮筒，并不放在最后一个房子的位置\n",
    "                        dp[i][j][l] = dp[l][j][l] + sum([abs(x-houses[l])for x in houses[l+1:i+1]] )\n",
    "                    else:\n",
    "                        # 有多个邮筒，它们放在不同的位置\n",
    "                        # 开始检索倒数第二个邮筒所有可能的位置\n",
    "                        tt = inf\n",
    "                        for ll in reversed(range(j-1, l)): \n",
    "                            t = dp[ll][j-1][ll] + sum([min(abs(x-houses[ll]),abs(x-houses[l]))for x in houses[ll+1:i+1]] )\n",
    "                            tt = min(t,tt)\n",
    "                        dp[i][j][l] = tt\n",
    "        return min(dp[n-1][k-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        houses.sort()\n",
    "        dp = [[[0] * (k + 1) for _ in range(len(houses))] for i in range(len(houses))]\n",
    "        for i in range(len(houses)):\n",
    "            dp[i][i][1] = 0\n",
    "            x = 0\n",
    "            for j in range(i + 1, len(houses)):\n",
    "                if (j - i) % 2 == 1:\n",
    "                    x += houses[j] - houses[j - 1]\n",
    "                    dp[i][j][1] = x + dp[i][j - 1][1]\n",
    "                else:\n",
    "                    x += houses[j] - houses[j - 1]\n",
    "                    x -= houses[i + (j - i) // 2] - houses[i + (j - i) // 2 - 1]\n",
    "                    dp[i][j][1] = x + dp[i][j - 1][1]\n",
    "        for i in range(2, k + 1):\n",
    "            for j in range(len(houses)):\n",
    "                for l in range(j + 1, len(houses)):\n",
    "                    dp[j][l][i] = min([dp[j][m][i - 1] + dp[m + 1][l][1] for m in range(j, l)])\n",
    "        return dp[0][len(houses) - 1][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        houses.sort()\n",
    "\n",
    "        # 前ii个位置放kk个油桶的最小距离和, 状态转移时候考虑房子的分组，同一组对应的邮箱就放在中位数位置\n",
    "        # min_dis表示ii+1位置的房子到其分组的中位数位置的距离\n",
    "        @lru_cache(typed=False, maxsize=12800000000)\n",
    "        def dp(ii, kk, min_dis):\n",
    "            if kk == 1:\n",
    "                start = 0\n",
    "                mid = (start + ii) // 2\n",
    "                if min_dis is not None and houses[ii+1] - houses[mid] < min_dis:\n",
    "                    return 0x7fffffff\n",
    "                else:\n",
    "                    sum = 0\n",
    "                    for i in range(start, ii+1):\n",
    "                        sum += abs(houses[i] - houses[mid])\n",
    "                    return sum\n",
    "            else:\n",
    "                ans = 0x7fffffff\n",
    "                for start in range(ii, kk-2, -1):\n",
    "                    mid = (start + ii) // 2\n",
    "                    if min_dis is not None and houses[ii+1] - houses[mid] < min_dis:\n",
    "                        continue\n",
    "\n",
    "                    sum = 0\n",
    "                    for i in range(start, ii+1):\n",
    "                        sum += abs(houses[i] - houses[mid])\n",
    "                    \n",
    "                    ret = dp(start-1, kk-1, houses[mid] - houses[start])\n",
    "                    if ret != 0x7fffffff:\n",
    "                        ans = min(ans, ret + sum)\n",
    "                return ans\n",
    "\n",
    "        return dp(len(houses)-1, k, None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], kk: int) -> int:\n",
    "        houses.sort()\n",
    "        n = len(houses) \n",
    "        f = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]\n",
    "\n",
    "        for lenn in range(2, n + 1): \n",
    "            for i in range(n + 1 - lenn): \n",
    "                j = i + lenn - 1 \n",
    "                for k in range(kk + 1): \n",
    "                    if k > lenn: continue\n",
    "                    if k == 1: f[i][j][k] = houses[j] - houses[i] + f[i + 1][j - 1][k]\n",
    "                    else: \n",
    "                        f[i][j][k] = inf\n",
    "                        for t in range(i + k - 1, j + 1): \n",
    "                            f[i][j][k] = min(f[i][j][k], f[i][t - 1][k - 1] + f[t][j][1])\n",
    "        \n",
    "        return f[0][n - 1][kk]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        length = len(houses)\n",
    "        houses.sort()\n",
    "        if length <= k:\n",
    "            return 0\n",
    "\n",
    "        def find_min_distance(points:List[int]):\n",
    "            mid = math.floor(len(points)/2)        \n",
    "            return sum([abs(p-points[mid]) for p in points])\n",
    "\n",
    "        dp = np.zeros((length,k))\n",
    "        for i in range(length):\n",
    "            dp[i][0] = find_min_distance(houses[:i+1])\n",
    "\n",
    "       \n",
    "        for loop in range(1,k):\n",
    "            for i in range(length):\n",
    "                if i <= loop:\n",
    "                    dp[i][loop] = 0\n",
    "                else:\n",
    "                    dp[i][loop] = 0\n",
    "                    prev_loop  = loop -1\n",
    "                    temp = []\n",
    "                    for j in range(prev_loop,i):\n",
    "                        temp.append(dp[j][prev_loop]+find_min_distance(houses[j+1:i+1]))\n",
    "                    dp[i][loop] = min(temp)\n",
    "        return int(dp[length-1][k-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        houses.sort()\n",
    "        n = len(houses)\n",
    "        dp = [[[inf] * n for _ in range(n)] for _ in range(k)]\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                l = j - i + 1\n",
    "                if l % 2:\n",
    "                    point = houses[i + l//2]\n",
    "                else:\n",
    "                    point = (houses[i + l//2 - 1] + houses[i + l//2]) // 2\n",
    "                dp[0][i][j] = sum(abs(p - point) for p in houses[i:j+1])\n",
    "            dp[0][i][i] = 0\n",
    "        for m in range(1, k):\n",
    "            for i in range(n):\n",
    "                for j in range(i + 1, n):\n",
    "                    dp[m][i][j] = min(dp[0][i][k] + dp[m-1][k+1][j] for k in range(i, j))\n",
    "        return dp[k-1][0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        houses.sort()\n",
    "        num = len(houses)\n",
    "        # w[i, j] 为从i+1个开始，到j个house的放1个邮筒的最小值\n",
    "        import numpy as np\n",
    "        w = np.zeros((num, num))\n",
    "        dp = np.zeros((num, k))\n",
    "        # dp[i, j] 为到第i个house放j个邮筒的最小值\n",
    "        from collections import defaultdict\n",
    "        result = defaultdict(list)\n",
    "\n",
    "        for i in range(num):\n",
    "            for j in range(i + 1, num):\n",
    "                w[i, j] = w[i, j - 1] + houses[j] - houses[(j + i) // 2]\n",
    "        # 初始化边界值\n",
    "        for ss in range(num):\n",
    "            if ss < k:\n",
    "                dp[ss, ss] = 0\n",
    "            dp[ss, 0] = w[0, ss]\n",
    "        # 两个状态转移方程\n",
    "        # w[l, r] = w[l +1, r - 1] + h[r] - h[l] = w[l, r -1 ] + h[r] - h[(r + l) /2]\n",
    "        # f[i][j] = min(f[i0][j -1 ] + w(i0, i))\n",
    "        for ii in range(0, num):\n",
    "            if ii < 1:\n",
    "                continue\n",
    "            for jj in range(1, k):\n",
    "                if jj >= ii:\n",
    "                    continue\n",
    "                dp[ii, jj] = 999999999\n",
    "                for kk in range(jj - 1, ii):\n",
    "                    dp[ii, jj] = min(dp[ii, jj], dp[kk][jj - 1] + w[kk + 1, ii])\n",
    "        # print(dp[num - 1, k - 1])\n",
    "        return int(dp[num - 1, k - 1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        houses.sort()\n",
    "        num = len(houses)\n",
    "        # w[i, j] 为从i+1个开始，到j个house的放1个邮筒的最小值\n",
    "        import numpy as np\n",
    "        w = np.zeros((num, num))\n",
    "        dp = np.zeros((num, k))\n",
    "        # dp[i, j] 为到第i个house放j个邮筒的最小值\n",
    "        # from collections import defaultdict\n",
    "        # result = defaultdict(list)\n",
    "\n",
    "        for i in range(num):\n",
    "            for j in range(i + 1, num):\n",
    "                w[i, j] = w[i, j - 1] + houses[j] - houses[(j + i) // 2]\n",
    "\n",
    "        # 两个状态转移方程\n",
    "        # w[l, r] = w[l +1, r - 1] + h[r] - h[l] = w[l, r -1 ] + h[r] - h[(r + l) /2]\n",
    "        # f[i][j] = min(f[i0][j -1 ] + w(i0, i))\n",
    "        for ii in range(0, num):\n",
    "            dp[ii, 0] = w[0, ii]\n",
    "            if ii < 1:\n",
    "                continue\n",
    "            for jj in range(1, min(k, num)):\n",
    "                if jj >= ii:\n",
    "                    continue\n",
    "                dp[ii, jj] = 999999\n",
    "                for kk in range(jj - 1, ii):\n",
    "                    dp[ii, jj] = min(dp[ii, jj], dp[kk][jj - 1] + w[kk + 1, ii])\n",
    "        return int(dp[num - 1, k - 1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, houses: List[int], k: int) -> int:\n",
    "        import numpy as np\n",
    "        houses.sort()\n",
    "\n",
    "        n = len(houses)\n",
    "        partition_res = np.zeros((n, n))\n",
    "        for i in range(n):\n",
    "            partition_res[i, i] = 0\n",
    "            for j in range(i):\n",
    "                partition_res[j, i] = houses[i] - houses[j]\n",
    "                if j <= i - 2:\n",
    "                    partition_res[j, i] += partition_res[j + 1, i - 1]\n",
    "\n",
    "        states = np.full((len(houses) + 1, k + 1), -1)\n",
    "        states[0, 0] = 0\n",
    "\n",
    "        for i in range(1, len(houses) + 1):\n",
    "            for j in range(1, k + 1):\n",
    "                for m in range(1, i + 1):\n",
    "                    if states[m - 1, j - 1] >= 0:\n",
    "                        nv = states[m - 1, j - 1] + partition_res[m - 1, i - 1]\n",
    "                        if states[i, j] < 0 or nv < states[i, j]:\n",
    "                            states[i, j] = nv\n",
    "\n",
    "        return int(states[n, k])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        m,n = len(word1),len(word2)\n",
    "        # @cache\n",
    "        # def dfs(i,j):\n",
    "        #     if i < 0:\n",
    "        l = self.longestCommonSubsequence(word1,word2)\n",
    "        return m+n-2*l\n",
    "\n",
    "\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        m,n = len(text1),len(text2)\n",
    "        f = [[0] * (n+1) for _ in range(2)]\n",
    "        for i,x in enumerate(text1):\n",
    "            for j,y in enumerate(text2):\n",
    "                if x == y:\n",
    "                    f[(i+1)%2][j+1] = f[i%2][j] + 1\n",
    "                else:\n",
    "                    f[(i+1)%2][j+1] = max(f[i%2][j+1],f[(i+1)%2][j])\n",
    "        return f[m%2][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        m = len(word1)\n",
    "        n = len(word2)\n",
    "        # 记忆化搜索实现\n",
    "        # @cache\n",
    "        # def dfs(i, j):\n",
    "        #     if i < 0:\n",
    "        #         return j + 1\n",
    "        #     if j < 0:\n",
    "        #         return i + 1\n",
    "        #     if word1[i] == word2[j]:\n",
    "        #         return dfs(i - 1, j - 1)\n",
    "        #     else:\n",
    "        #         return min(dfs(i, j - 1), dfs(i - 1, j)) + 1\n",
    "        # return dfs(m - 1, n - 1)\n",
    "\n",
    "        # 使用dp数组实现\n",
    "        # dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        # # 初始化第一行\n",
    "        # dp[0] = list(range(n + 1))\n",
    "        # for i, x in enumerate(word1):\n",
    "        #     # 初始化第一列元素\n",
    "        #     dp[i + 1][0] = i + 1\n",
    "        #     for j, y in enumerate(word2):\n",
    "        #         if x == y:\n",
    "        #             dp[i + 1][j + 1] = dp[i][j]\n",
    "        #         else:\n",
    "        #             dp[i + 1][j + 1] = min(dp[i + 1][j], dp[i][j + 1]) + 1\n",
    "        # return dp[m][n]\n",
    "\n",
    "        # 对数组进行优化\n",
    "        # dp = [[0] * (n + 1) for _ in range(2)]\n",
    "        # # 初始化第一行\n",
    "        # dp[0] = list(range(n + 1))\n",
    "        # for i, x in enumerate(word1):\n",
    "        #     # 初始化第一列元素\n",
    "        #     dp[(i + 1) % 2][0] = i + 1\n",
    "        #     for j, y in enumerate(word2):\n",
    "        #         if x == y:\n",
    "        #             dp[(i + 1) % 2][j + 1] = dp[i % 2][j]\n",
    "        #         else:\n",
    "        #             dp[(i + 1) % 2][j + 1] = min(dp[(i + 1) % 2][j], dp[i % 2][j + 1]) + 1\n",
    "        # return dp[m % 2][n]\n",
    "\n",
    "\n",
    "        # 使用一维数组实现\n",
    "        dp = list(range(n + 1))\n",
    "        for i, x in enumerate(word1):\n",
    "            pre = dp[0]\n",
    "            # 初始化第一列元素\n",
    "            dp[0] += 1\n",
    "            for j, y in enumerate(word2):\n",
    "                tmp = dp[j + 1]\n",
    "                if x == y:\n",
    "                    dp[j + 1] = pre\n",
    "                else:\n",
    "                    dp[j + 1] = min(dp[j], dp[j + 1]) + 1\n",
    "                pre = tmp\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        n=len(word1)\n",
    "        m=len(word2)\n",
    "        res=0\n",
    "        dp=[0]*(n+1)\n",
    "        for i in range(1,1+m):\n",
    "            d=dp.copy()\n",
    "            for j in range(1,n+1):\n",
    "                if word2[i-1]==word1[j-1]:\n",
    "                    dp[j]=d[j-1]+1\n",
    "                    res=max(dp[j],res)\n",
    "                else:\n",
    "                    dp[j]=max(dp[j],dp[j-1])\n",
    "        return n+m-res*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        lw1, lw2 = len(word1), len(word2)\n",
    "        states = []\n",
    "        offset = 2\n",
    "        for i in range(lw1):\n",
    "            if word1[i] == word2[0]:\n",
    "                offset = 0\n",
    "            states.append(i + offset)\n",
    "        print(states)\n",
    "        for k in range(1, lw2):\n",
    "            old = states[0]\n",
    "            if states[0] == k+1 and word1[0] == word2[k]:\n",
    "                states[0] = k\n",
    "            else:\n",
    "                states[0] = states[0] + 1\n",
    "            for i in range(1, lw1):\n",
    "                tmp = states[i]\n",
    "                if word1[i] == word2[k]:\n",
    "                    states[i] = old\n",
    "                else:\n",
    "                    states[i] = min(states[i-1]+1, states[i]+1)\n",
    "                old = tmp\n",
    "            print(states)\n",
    "        return states[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        length1, length2 = len(word1), len(word2)\n",
    "        dp = [length1+length2] * (length1 + 1)\n",
    "        for i in range(length2):\n",
    "            temp = dp[:]\n",
    "            for j in range(1, length1+1):\n",
    "                if word2[i] == word1[j-1]:\n",
    "                    dp[j] = temp[j-1] -2\n",
    "                else:\n",
    "                    dp[j] = min(dp[j-1], dp[j])\n",
    "            print(dp)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        dp = [[0 for _ in range(len(word2))] for _ in range(len(word1))]\n",
    "        if word1[0]==word2[0]:\n",
    "            dp[0][0]=1\n",
    "        for j in range(1,len(word2)):\n",
    "            if word1[0] == word2[j]:\n",
    "                dp[0][j]=1\n",
    "            else:\n",
    "                dp[0][j]=dp[0][j-1]\n",
    "        for i in range(1,len(word1)):\n",
    "            if word1[i] == word2[0]:\n",
    "                dp[i][0]=1\n",
    "            else:\n",
    "                dp[i][0]=dp[i-1][0]\n",
    "\n",
    "        for i in range(1,len(word1)):\n",
    "            for j in range(1,len(word2)):\n",
    "                if word1[i] == word2[j]:\n",
    "                    dp[i][j]= dp[i-1][j-1]+1\n",
    "\n",
    "                else:\n",
    "                    dp[i][j]=max(dp[i-1][j],dp[i][j-1])\n",
    "\n",
    "        return len(word1)+len(word2)-2*dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        info = [[0 for j in range(len(word2))] for i in range(len(word1))]\n",
    "        \n",
    "        info[0][0] = 1 if word1[0] == word2[0] else 0\n",
    "        for j in range(1, len(word2)):\n",
    "            info[0][j] = max(info[0][j - 1], 1 if word1[0] == word2[j] else 0)\n",
    "        \n",
    "        for i in range(1, len(word1)):\n",
    "            info[i][0] = max(info[i - 1][0], 1 if word1[i] == word2[0] else 0)\n",
    "            for j in range(1, len(word2)):\n",
    "                info[i][j] = max(info[i - 1][j], info[i][j - 1])\n",
    "                if word1[i] == word2[j]:\n",
    "                    info[i][j] = max(info[i][j], info[i - 1][j - 1] + 1)\n",
    "        \n",
    "\n",
    "        return len(word1) + len(word2) - (info[-1][-1] << 1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        m,n = len(word1),len(word2)\n",
    "        dp = [[0 for _ in range(n+1)]for _ in range(m+1)]  #！！！\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "               \n",
    "                if word1[i-1] == word2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]+1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j],dp[i][j-1])\n",
    "        return m+n-2*dp[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        n1, n2 = len(word1), len(word2)\n",
    "        dp = [[0] * (n2+1) for _ in range(n1+1)]\n",
    "        for i in range(1, n1+1):\n",
    "            for j in range(1, n2+1):\n",
    "                if word1[i-1] == word2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i][j-1], dp[i-1][j])\n",
    "        k = dp[-1][-1]\n",
    "        return n1-k+n2-k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        n = len(word1)\n",
    "        m = len(word2)\n",
    "\n",
    "        dp = [[0] * (n+1) for _ in range(m+1)]\n",
    "\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if word1[j-1] == word2[i-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n",
    "\n",
    "        return m+n-(2*dp[-1][-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        if not word1:\n",
    "            return len(word2)\n",
    "        if not word2:\n",
    "            return len(word2)\n",
    "        \n",
    "        row = len(word1)\n",
    "        col = len(word2)\n",
    "        dp = [[0] * col for _ in range(row)]\n",
    "        #max_len = 0\n",
    "        if word1[0] == word2[0]:\n",
    "            dp[0][0] = 1\n",
    "        for i in range(1, row):\n",
    "            if word1[i] == word2[0]:\n",
    "                dp[i][0] = 1\n",
    "            else:\n",
    "                dp[i][0] = dp[i-1][0]\n",
    "            #max_len = max(max_len, dp[i][0])\n",
    "        \n",
    "        for i in range(1, col):\n",
    "            if word1[0] == word2[i]:\n",
    "                dp[0][i] = 1\n",
    "            else:\n",
    "                dp[0][i] = dp[0][i-1]\n",
    "            #max_len = max(max_len, dp[0][i])\n",
    "        \n",
    "        for i in range(1, row):\n",
    "            for j in range(1, col):\n",
    "                if word1[i] == word2[j]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n",
    "        return len(word1) + len(word2) - (2 * dp[-1][-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "\n",
    "        memo = {}\n",
    "\n",
    "        return self.dp(word1, len(word1) - 1, word2, len(word2) - 1, memo)\n",
    "\n",
    "    \n",
    "    def dp(self, word1, i, word2, j, memo):\n",
    "        if i < 0:\n",
    "            return j + 1\n",
    "\n",
    "        if j < 0:\n",
    "            return i + 1\n",
    "\n",
    "        key = (i, j)\n",
    "        if key in memo:\n",
    "            return memo[key]\n",
    "\n",
    "        if word1[i] == word2[j]:\n",
    "            memo[key] = self.dp(word1, i - 1, word2, j - 1, memo)\n",
    "        else:\n",
    "            memo[key] = min(self.dp(word1, i - 1, word2, j, memo), self.dp(word1, i, word2, j - 1, memo)) + 1\n",
    "\n",
    "        return memo[key] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        grid = [[0]*(len(word2)+1) for i in range(len(word1)+1)]\n",
    "        for i in range(len(word1)):\n",
    "            for j in range(len(word2)):\n",
    "                if word1[i]==word2[j]:\n",
    "                    grid[i+1][j+1] = grid[i][j]+1\n",
    "                else:\n",
    "                    grid[i+1][j+1] = max(grid[i+1][j], grid[i][j+1])\n",
    "        print(grid[-1][-1])\n",
    "        return len(word1)+len(word2)-2*grid[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, text1: str, text2: str) -> int:\n",
    "        l1 = len(text1)\n",
    "        l2 = len(text2)\n",
    "        dp = [[0] * (l1 + 1) for i in range(l2 + 1) ]\n",
    "        for i in range(1,l1 + 1):\n",
    "            for j in range(1,l2 + 1):\n",
    "                if text1[i - 1] == text2[j -1 ]:\n",
    "                    dp[j][i] = dp[j-1][i-1] + 1\n",
    "                else:\n",
    "                    dp[j][i] = max(dp[j-1][i],dp[j][i-1]) \n",
    "        return l1 + l2 - 2 * dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        size1 = len(word1)\n",
    "        size2 = len(word2)\n",
    "        # 求word1[:i-1],word[:j-1]的最长公共子序列\n",
    "        dp = [[0]*(size2+1) for i in range(size1+1)]\n",
    "        for i in range(1,size1+1):\n",
    "            for j in range(1,size2+1):\n",
    "                if word1[i-1] == word2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]+1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j],dp[i][j-1])\n",
    "        return size1+size2-dp[-1][-1]*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        # 以i-1, j-1为结尾的重复个数\n",
    "        dp = [[0]*(len(word1)+1) for _ in range(len(word2)+1)]\n",
    "        max_value = 0\n",
    "        for i in range(1,  len(word2)+1):\n",
    "            for j in range(1, len(word1)+1):\n",
    "                if word1[j-1] == word2[i-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]+1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i][j-1], dp[i-1][j])        \n",
    "        return len(word1)+len(word2)-2*dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        m, n = len(word1), len(word2)\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if word1[i] == word2[j]:\n",
    "                    dp[i + 1][j + 1] = dp[i][j] + 1\n",
    "                else:\n",
    "                    dp[i + 1][j + 1] = max(dp[i][j + 1] , dp[i + 1][j])\n",
    "        return m + n - dp[m][n] * 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        m, n = len(word1), len(word2)\n",
    "        dp = [[0]*(1+m) for _ in range(1+n)]\n",
    "        #dp[0][0] = 1 \n",
    "        for i in range(1, 1+n):\n",
    "            for j in range(1, 1+m):\n",
    "                if word1[j-1] ==word2[i-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]+1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n",
    "        print(dp[-1][-1])\n",
    "\n",
    "        return m+n-2*dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        # 法1：先找最长公共子序列\n",
    "        # dp[i][j]表示以i-1,j-1结尾的两个字符串的最长公共子序列的长度\n",
    "        l1,l2=len(word1),len(word2)\n",
    "        dp = [[0]*(l2+1) for _ in range(l1+1)]\n",
    "        for i in range(1,l1+1):\n",
    "            for j in range(1,l2+1):\n",
    "                if(word1[i-1]==word2[j-1]):\n",
    "                    dp[i][j]=dp[i-1][j-1]+1\n",
    "                else:\n",
    "                    dp[i][j]=max(dp[i][j-1],dp[i-1][j])\n",
    "                print(dp[i][j])\n",
    "        \n",
    "        return l1+l2-dp[l1][l2]*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dp(self,s1,i,s2,j):\n",
    "        if i==-1: return j+1\n",
    "        if j==-1: return i+1\n",
    "        if (i,j) in self.memo:\n",
    "            return self.memo[(i,j)]\n",
    "        if s1[i]==s2[j]:\n",
    "            self.memo[(i,j)]=self.dp(s1,i-1,s2,j-1)\n",
    "        else:\n",
    "            self.memo[(i,j)]=min(self.dp(s1,i-1,s2,j)+1,self.dp(s1,i,s2,j-1)+1)\n",
    "        return self.memo[(i,j)] \n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        m,n=len(word1),len(word2)\n",
    "        self.memo={}\n",
    "        return self.dp(word1,m-1,word2,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dp(self,word1,i,word2,j,memo):\n",
    "        if i==-1:\n",
    "            return j+1\n",
    "        if j==-1:\n",
    "            return i+1\n",
    "        if memo[i][j] != -1:\n",
    "            return memo[i][j]\n",
    "        if word1[i] == word2[j]:\n",
    "            memo[i][j] = self.dp(word1,i-1,word2,j-1,memo)\n",
    "        else:\n",
    "            memo[i][j] = min(\n",
    "                self.dp(word1,i,word2,j-1,memo)+1,\n",
    "                self.dp(word1,i-1,word2,j,memo)+1\n",
    "            )\n",
    "        return memo[i][j]\n",
    "\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        memo = [[-1 for _ in range(len(word2))] for _ in range(len(word1))]\n",
    "        return self.dp(word1,len(word1)-1,word2,len(word2)-1,memo)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # dp(t1, i, t2, j) 返回 t1[:i+1] 和 t2[:j+1] 需要的最小步数\n",
    "    def dp(self, t1, i, t2, j):\n",
    "        if i == -1:\n",
    "            return j + 1\n",
    "        if j == -1:\n",
    "            return i + 1\n",
    "        if self.memo[i][j] != -1:\n",
    "            return self.memo[i][j]\n",
    "        if t1[i] == t2[j]:\n",
    "            self.memo[i][j] = self.dp(t1, i-1, t2, j-1)\n",
    "        else:\n",
    "            self.memo[i][j] =  min(self.dp(t1, i, t2, j-1) + 1, self.dp(t1, i-1, t2, j) + 1)\n",
    "        return self.memo[i][j]\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        self.memo = [[-1] * len(word2) for _ in range(len(word1))]\n",
    "        return self.dp(word1, len(word1)-1, word2, len(word2)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://mp.weixin.qq.com/s/ZhPEchewfc03xWv9VP3msg\n",
    "# 删除的之后，剩下的结果不就是它俩的最长公共子序列嘛！\n",
    "# 删除的结果不就是它俩的最长公共子序列嘛！同题目1143,详细解释见1143题\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        if not word1:\n",
    "            return len(word2)\n",
    "        if not word2:\n",
    "            return len(word1)\n",
    "\n",
    "        m, n = len(word1), len(word2)\n",
    "        lcs = self.longestCommonSubsequence(word1, word2)\n",
    "\n",
    "        return m - lcs + (n - lcs)\n",
    "\n",
    "    \n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        m, n = len(text1), len(text2)\n",
    "        memo = [[-1] * n for _ in range(m)] # 这里m和n的顺序无所谓，只要和后面循环时或者递归时i j位置一致就行\n",
    "\n",
    "        return self.dp(memo, text1, 0, text2, 0)\n",
    "\n",
    "    def dp(self, memo, text1, i, text2, j):\n",
    "        # base case\n",
    "        if i == len(text1) or j == len(text2):\n",
    "            return 0\n",
    "        \n",
    "        if memo[i][j] != -1:\n",
    "            return memo[i][j]\n",
    "        \n",
    "        if text1[i] == text2[j]:\n",
    "            memo[i][j] = self.dp(memo, text1, i+1, text2, j+1) + 1\n",
    "        else:\n",
    "            memo[i][j] = max(\n",
    "                self.dp(memo, text1, i+1, text2, j),\n",
    "                self.dp(memo, text1, i, text2, j+1),\n",
    "                # self.dp(memo, text1, i+1, text2, j+1) # 这一句可以不写，会节约一点时间，不写的原因见上面\n",
    "            )\n",
    "            \n",
    "        return memo[i][j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.memo=[]\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        n, m = len(word1), len(word2)\n",
    "        self.memo = [[-1]*(m+1) for _ in range(n+1)]\n",
    "        return self.dp(word1,n,word2, m)\n",
    "    def dp(self , word1, i, word2, j):\n",
    "        if i == 0:\n",
    "            return j\n",
    "        if j == 0:\n",
    "            return i\n",
    "        if self.memo[i][j] != -1:\n",
    "            return self.memo[i][j]\n",
    "        if word1[i-1] == word2[j-1]:\n",
    "            self.memo[i][j] = self.dp(word1,i-1, word2, j-1)\n",
    "        else:\n",
    "            self.memo[i][j] = min(self.dp(word1,i-1,word2,j), self.dp(word1,i,word2,j-1))+1\n",
    "        return self.memo[i][j]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        n1 = len(word1)\n",
    "        n2 = len(word2)\n",
    "        dp_table = [[-1]*(n2+1) for _ in range(n1+1)]\n",
    "\n",
    "        def dp(w1, w2, p1, p2):\n",
    "            if dp_table[p1][p2] != -1:\n",
    "                return dp_table[p1][p2]\n",
    "            res = -1\n",
    "            if p1 == len(w1):\n",
    "                res = len(w2) - p2\n",
    "            elif p2 == len(w2):\n",
    "                res = len(w1) - p1\n",
    "            elif w1[p1] == w2[p2]:\n",
    "                res = dp(w1, w2, p1+1, p2+1)\n",
    "            else:\n",
    "                res = 1+min(\n",
    "                    dp(w1, w2, p1+1, p2),\n",
    "                    dp(w1, w2, p1, p2+1)\n",
    "                )\n",
    "            dp_table[p1][p2] = res\n",
    "            return res\n",
    "        return dp(word1, word2, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        n1 = len(word1)\n",
    "        n2 = len(word2)\n",
    "        dp_table = [[-1]*(n2+1) for _ in range(n1+1)]\n",
    "\n",
    "        def dp(w1, w2, p1, p2):\n",
    "            if dp_table[p1][p2] != -1:\n",
    "                return dp_table[p1][p2]\n",
    "            res = -1\n",
    "            if p1 == len(w1):\n",
    "                res = len(w2) - p2\n",
    "            elif p2 == len(w2):\n",
    "                res = len(w1) - p1\n",
    "            elif w1[p1] == w2[p2]:\n",
    "                res = dp(w1, w2, p1+1, p2+1)\n",
    "            else:\n",
    "                res = 1+min(\n",
    "                    dp(w1, w2, p1+1, p2),\n",
    "                    dp(w1, w2, p1, p2+1)\n",
    "                )\n",
    "            dp_table[p1][p2] = res\n",
    "            return res\n",
    "        return dp(word1, word2, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        \n",
    "        dp = [[0 for i in range(len(word2) + 1)] for i in range(len(word1) + 1)]\n",
    "\n",
    "        for i in range(len(word1) + 1):\n",
    "            dp[i][0] = i\n",
    "\n",
    "        for i in range(len(word2) + 1):\n",
    "            dp[0][i] = i\n",
    "\n",
    "        for i in range(len(word1)):\n",
    "            for j in range(len(word2)):\n",
    "                if word1[i] == word2[j]:\n",
    "                    dp[i+1][j+1] = dp[i][j]\n",
    "                \n",
    "                else:\n",
    "                    dp[i+1][j+1] = min(dp[i+1][j], dp[i][j+1]) + 1\n",
    "\n",
    "        return dp[-1][-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        dp = [[0] * (len(word2)+1) for _ in range(len(word1)+1)]\n",
    "        for i in range(len(word1)+1):\n",
    "            dp[i][0] = i\n",
    "        for j in range(len(word2)+1):\n",
    "            dp[0][j] = j\n",
    "        for i in range(1, len(word1)+1):\n",
    "            for j in range(1, len(word2)+1):\n",
    "                if word1[i-1] == word2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j-1]+2, dp[i-1][j]+1, dp[i][j-1]+1)\n",
    "        return dp[-1][-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "\n",
    "        m, n = len(word1), len(word2)\n",
    "\n",
    "        dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]\n",
    "\n",
    "        for i in range(m + 1):\n",
    "            dp[i][0] = i\n",
    "        for j in range(n + 1):\n",
    "            dp[0][j] = j\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if word1[i - 1] == word2[j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j - 1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1\n",
    "\n",
    "        return dp[m][n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        M, N = len(word1), len(word2)\n",
    "        dp = [ [ inf ] * (N+1) for _ in range(M+1)]\n",
    "        for i in range(M+1):\n",
    "            for j in range(N+1):\n",
    "                if i == 0:\n",
    "                    dp[i][j] = j\n",
    "                elif j == 0:\n",
    "                    dp[i][j] = i\n",
    "                else:\n",
    "                    if word1[i-1] == word2[j-1]:\n",
    "                        dp[i][j] = min(dp[i][j], dp[i-1][j-1], dp[i-1][j]+1, dp[i][j-1] + 1)\n",
    "                    else:\n",
    "                        dp[i][j] = min(dp[i][j], dp[i-1][j]+1, dp[i][j-1] + 1)\n",
    "        # print(dp)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        m = len(word1)\n",
    "        n = len(word2)\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            dp[i][0] = i\n",
    "        for i in range(1, n + 1):\n",
    "            dp[0][i] = i\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if word1[i - 1] == word2[j - 1]:\n",
    "                    dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1])\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1)\n",
    "        return dp[m][n]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        n1, n2 = len(word1), len(word2)\n",
    "        dp = [[i for i in range(n2+1)] for _ in range(n1+1)]\n",
    "        for i in range(n1+1):\n",
    "            dp[i][0] = i\n",
    "        for i in range(1, n1+1):\n",
    "            for j in range(1, n2+1):\n",
    "                if word1[i-1] == word2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = min(2+dp[i-1][j-1], 1+dp[i-1][j], 1+dp[i][j-1])\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        m, n = len(word1), len(word2)\n",
    "        dp = [[0 for j in range(n)] for i in range(m)]\n",
    "        \n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if word1[i] == word2[j]:\n",
    "                    if i == 0 or j == 0:\n",
    "                        dp[i][j] = 1\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i-1][j-1] + 1\n",
    "                else:\n",
    "                    if i == 0:\n",
    "                        dp[i][j] = dp[i][j-1]\n",
    "                    elif j == 0:\n",
    "                        dp[i][j] = dp[i-1][j]\n",
    "                    else:\n",
    "                        dp[i][j] = max(dp[i][j-1], dp[i-1][j])\n",
    "\n",
    "        print(dp)\n",
    "        return m + n - 2*dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        l1=len(word1)\n",
    "        l2=len(word2)\n",
    "        dp=[[0 for _ in range(l2+1)] for _ in range(l1+1)]\n",
    "        # for i in range(l1+1):\n",
    "        #     dp[i][0]=1\n",
    "        for i in range(l1):\n",
    "            for j in range(l2):\n",
    "                if word1[i]==word2[j]:\n",
    "                    dp[i+1][j+1]=max(dp[i][j]+1,dp[i][j+1])\n",
    "                else:\n",
    "                    dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])\n",
    "        print(dp)\n",
    "        return l1+l2-2*dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        # 思路二，最长公共子序列\n",
    "\n",
    "        # dp[i][j]代表以i-1为尾的word1和以j-1为尾的word2相同所需的最长公共子序列\n",
    "        # 初始化\n",
    "        dp=[[0]*(len(word2)+1) for i in range(len(word1)+1)]\n",
    "\n",
    "        res=0\n",
    "        # 递推公式\n",
    "        # 相同: dp[i][j]=dp[i-1][j-1]+dp[i-1][j]\n",
    "        # 不相同: dp[i][j]=dp[i-1][j-1]\n",
    "        # 遍历顺序：正序\n",
    "        for i in range(1,len(word1)+1):\n",
    "            for j in range(1,len(word2)+1):\n",
    "                if(word1[i-1]==word2[j-1]):\n",
    "                    dp[i][j]=dp[i-1][j-1]+1\n",
    "                else:\n",
    "                    dp[i][j]=max(dp[i-1][j],dp[i][j-1])\n",
    "                if dp[i][j]>res:\n",
    "                    res=dp[i][j]\n",
    "        print(dp)\n",
    "        return len(word1+word2)-2*res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    1. dp[i][j]: i-1 和j-1结尾的两个字单词， 最小步数\n",
    "    2. \n",
    "    if word1[i-1] == word2[j-1]:\n",
    "        dp[i][j] = dp[i-1][j-1]\n",
    "    else:\n",
    "        dp[i][j] = min(dp[i][j-1] + 1, dp[i-1][j] + 1, dp[i-1][j-1] + 2)\n",
    "\n",
    "    3. init\n",
    "    dp[0][0] = 0\n",
    "    for i in range(1, n1):\n",
    "        dp[i][0] = i\n",
    "    for j in range(1, n2):\n",
    "        dp[0][j] = j\n",
    "    '''\n",
    "    def minDistance1(self, word1: str, word2: str) -> int:\n",
    "        n1, n2 = len(word1) + 1, len(word2) + 1\n",
    "\n",
    "        dp = [[0]*n2 for _ in range(n1)]\n",
    "        dp[0][0] = 0\n",
    "        for i in range(1, n1):\n",
    "            dp[i][0] = i\n",
    "        for j in range(1, n2):\n",
    "            dp[0][j] = j\n",
    "\n",
    "        for i in range(1, n1):\n",
    "            for j in range(1, n2):\n",
    "                if word1[i-1] == word2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i][j-1] + 1, dp[i-1][j] + 1, dp[i-1][j-1] + 2)\n",
    "        return dp[n1-1][n2-1]\n",
    "\n",
    "        '''转化为求最长公共子序列的长度， 然后需要最少操作数： len(word1) + len(word2) - 2 *dp[n1-1][n2-1]\n",
    "\n",
    "        '''\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        n1, n2 = len(word1) + 1, len(word2) + 1\n",
    "        dp = [[0]*n2 for _ in range(n1)]\n",
    "\n",
    "        for i in range(1, n1):\n",
    "            for j in range(1, n2):\n",
    "                # print(i, ' ', j)\n",
    "                if word1[i-1] == word2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n",
    "        print((dp))\n",
    "        return len(word1) + len(word2) - 2 * dp[n1-1][n2-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        len1,len2=len(word1),len(word2)\n",
    "        dp=[[0]*(len1+1) for _ in range(len2+1)]\n",
    "        # print(dp)\n",
    "        for j in range(len1+1):\n",
    "            dp[0][j]=j\n",
    "        for i in range(len2+1):\n",
    "            dp[i][0]=i\n",
    "        # print(dp)\n",
    "        for i in range(1,len2+1):\n",
    "            for j in range(1,len1+1):\n",
    "                if word1[j-1]==word2[i-1]:\n",
    "                    dp[i][j]=dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j]=min(dp[i-1][j-1]+2,dp[i-1][j]+1,dp[i][j-1]+1)\n",
    "        print(dp)\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        t=word1\n",
    "        s=word2\n",
    "        m=len(word1)+1\n",
    "        n=len(word2)+1\n",
    "        dp=[[ 0 for j in range(n)] for i in range(m)]\n",
    "        for j in range(0,n):\n",
    "            dp[0][j]=j\n",
    "        for i in range(0,m):\n",
    "            dp[i][0]=i\n",
    "        dp[0][0]=0\n",
    "\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                if t[i-1]==s[j-1]:\n",
    "                    dp[i][j]=dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j]=min(dp[i][j-1]+1,dp[i-1][j]+1)\n",
    "            # mx=max(mx,dp[i])\n",
    "\n",
    "        print(dp)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        m1 = len(word1)\n",
    "        m2 = len(word2)\n",
    "        dp = [[0 for i in range(m2+1)]for i in range(m1+1)]\n",
    "        for i in range(m1+1):\n",
    "            dp[i][0] = i\n",
    "        for j in range(m2+1):\n",
    "            dp[0][j] = j\n",
    "        res = float('inf')\n",
    "        for i in range(1, m1+1):\n",
    "            for j in range(1, m2+1):\n",
    "                if word1[i-1] == word2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1,dp[i-1][j-1]+2)\n",
    "                res = min(res, dp[i][j])\n",
    "        print(res)\n",
    "        print(dp)\n",
    "        return dp[m1][m2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        # 相当于是返回最长的公共子序列（非连续），不需要用动态规划，直接转换成数组并且sort，然后双指针递归。\n",
    "        # 上面的做法不对，一定是要有序的公共子序列，单独只是个子序列不行，还是得动态规划：dp是二维的，分别代表1和2的i，j为尾巴的公共子数组的长度\n",
    "        dp = [[0 for _ in word2] for _ in word1]\n",
    "        for i in range(len(word1)):\n",
    "            if word2[0] in word1[:i+1]:\n",
    "                dp[i][0] = 1\n",
    "        for i in range(len(word1)):\n",
    "            for j in range(1,len(word2)):\n",
    "                if word2[j] not in word1[:i+1]:\n",
    "                    dp[i][j] = dp[i][j-1]\n",
    "                else:\n",
    "                    idx = word1[:i+1].rfind(word2[j])\n",
    "                    if idx != 0:\n",
    "                        dp[i][j] = max(dp[i][j-1], dp[idx-1][j-1]+1)\n",
    "                    else:\n",
    "                        dp[i][j] = max(dp[i][j-1], 1)\n",
    "                    \n",
    "        print(dp)\n",
    "        return len(word1)+len(word2)-2*max([max(dp[i]) for i in range(len(dp))])\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        '''\n",
    "        1、确定dp数组以及下标的含义：\n",
    "           dp[i][j]：表示以word1[i-1]为结尾的子序列，和以word2[j-1]为结尾的子序列，最长公共子序列的长度为dp[i][j]。\n",
    "        2、递推公式：\n",
    "           if word1[i-1] == word2[j-1]:\n",
    "               dp[i][j] = dp[i-1][j-1] + 1\n",
    "           else:\n",
    "               dp[i][j] = dp[i-1][j-1]\n",
    "        '''\n",
    "        # 定义dp数组\n",
    "        dp = [[0] * (len(word2) + 1) for _ in range(len(word1) + 1)]\n",
    "        print('初始dp', dp)\n",
    "        # 更新状态\n",
    "        for i in range(1, len(word1) + 1):\n",
    "            for j in range(1, len(word2) + 1):\n",
    "                if word1[i - 1] == word2[j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j - 1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])\n",
    "        print('更新dp', dp)\n",
    "        return len(word1) + len(word2) - 2 * dp[len(word1)][len(word2)]                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        m, n = len(word1), len(word2)\n",
    "\n",
    "        dp = [[0] * (n+1) for _ in range(m+1)]\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            dp[i][0] = i\n",
    "        for j in range(1, n + 1):\n",
    "            dp[0][j] = j\n",
    "\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if word1[i-1] == word2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1\n",
    "        return dp[m][n]\n",
    "\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        if len(word1) == 0:\n",
    "            return len(word2)\n",
    "        if len(word2) == 0:\n",
    "            return len(word1)\n",
    "\n",
    "        dp = [[0 for _ in range(len(word2) + 1)] for _ in range(len(word1) + 1)]\n",
    "\n",
    "        for _ in range(len(word2) + 1):\n",
    "            dp[0][_] = _ \n",
    "        for _ in range(len(word1) + 1):\n",
    "            dp[_][0] = _\n",
    "\n",
    "        print(dp)\n",
    "\n",
    "        for i in range(1, len(word1) + 1):\n",
    "            for j in range(1, len(word2) + 1):\n",
    "                if word1[i - 1] == word2[j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j - 1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j-1] + 2)\n",
    "        \n",
    "        print(dp)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        # dp[i][j]表示word1[0:i-1]和word2[0:j-1]的编辑距离\n",
    "        m, n = len(word1)+1, len(word2)+1\n",
    "        dp = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(1, m):\n",
    "            dp[i][0] = i\n",
    "        for j in range(1, n):\n",
    "            dp[0][j] = j       \n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                if word1[i-1] == word2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j-1]+2, dp[i-1][j]+1, dp[i][j-1]+1) \n",
    "        print(dp)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "\n",
    "        len1 = len(word1)\n",
    "        len2 = len(word2)\n",
    "\n",
    "        dp = [[0] * (len2 + 1) for _ in range(len1 + 1)]\n",
    "\n",
    "        # 注意初始化，定义为对应长度的字符串到空字符串的操作次数\n",
    "        for i in range(1, len1 + 1):\n",
    "            dp[i][0] = i\n",
    "        for j in range(1, len2 + 1):\n",
    "            dp[0][j] = j\n",
    "\n",
    "        for i in range(1, len1 + 1):\n",
    "            for j in range(1, len2 + 1):\n",
    "\n",
    "                # x = len1 - i\n",
    "                # y = len2 - j\n",
    "\n",
    "                if word1[i - 1] == word2[j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j - 1]\n",
    "                \n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1\n",
    "        \n",
    "        print(dp)\n",
    "        \n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        dp = [[0]*(len(word2)+1) for _ in range(len(word1)+1)]\n",
    "        for i in range(len(word1)+1):\n",
    "            dp[i][0] = i\n",
    "        for j in range(len(word2)+1):\n",
    "            dp[0][j] = j\n",
    "        for i in range(1, len(word1)+1):\n",
    "            for j in range(1, len(word2)+1):\n",
    "                if word1[i-1] == word2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j-1] + 2, dp[i-1][j]+1, dp[i][j-1]+1)\n",
    "        print(dp)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        dp = [[float('inf')]*(len(word2)+1) for _ in range(len(word1)+1)]\n",
    "        for i in range(len(word1)+1):\n",
    "            dp[i][0] = i\n",
    "        for j in range(len(word2)+1):\n",
    "            dp[0][j] = j\n",
    "        # dogp\n",
    "        # dog\n",
    "        \n",
    "        for i in range(1, len(word1)+1):\n",
    "            for j in range(1, len(word2)+1):\n",
    "                if word1[i-1] == word2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j],dp[i][j-1])+1\n",
    "        print(dp)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        if not (word1 or word2):\n",
    "            return 0\n",
    "        dp = [list(range(0,len(word1)+1)) for j in range(len(word2)+1)]\n",
    "        for i in range(len(word2)+1):\n",
    "            dp[i][0] = i\n",
    "        # dp = [[1]*(len(word1)+1) for j in range(len(word2)+1)]\n",
    "        dp[0][0] = 0\n",
    "        for i in range(1,len(word1)+1):\n",
    "            for j in range(1,len(word2)+1):\n",
    "                if word1[i-1] == word2[j-1]:\n",
    "                    dp[j][i] = dp[j-1][i-1]\n",
    "                else:\n",
    "                    dp[j][i] = min(dp[j-1][i-1]+2,dp[j][i-1]+1,dp[j-1][i]+1)\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# # like edit distance.\n",
    "# class Solution:\n",
    "#     def minDistance(self, word1: str, word2: str) -> int:\n",
    "#         len1, len2 = len(word1), len(word2)\n",
    "        \n",
    "#         dp_matrix = [[0 for _ in range(len2+1)] for _ in range(len1+1)]\n",
    "\n",
    "#         for i in range(len1+1):\n",
    "#             dp_matrix[i][0] = i \n",
    "#         for j in range(len2+1):\n",
    "#             dp_matrix[0][j] = j\n",
    "        \n",
    "#         for i in range(1, len1+1, 1):\n",
    "#             for j in range(1, len2+1, 1):\n",
    "#                 if word1[i-1]==word2[j-1]:\n",
    "#                     dp_matrix[i][j] = dp_matrix[i-1][j-1]\n",
    "#                 else:\n",
    "#                     dp_matrix[i][j] = min(\n",
    "#                         dp_matrix[i][j-1] + 1,\n",
    "#                         dp_matrix[i-1][j] + 1\n",
    "#                     )\n",
    "#         print(dp_matrix)\n",
    "#         return dp_matrix[len(word1)][len(word2)]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        len1, len2 = len(word1), len(word2)\n",
    "        if len1 == 0 or len2 == 0:\n",
    "            return max(len1, len2)\n",
    "        \n",
    "        dp = [[0 for _ in range(len2+1)] for _ in range(len1+1)]\n",
    "        \n",
    "        dp = [[0]*(len2+1) for _ in range(len1+1)]\n",
    "\n",
    "        for i in range(len1+1):\n",
    "            dp[i][0] = i \n",
    "        \n",
    "        for j in range(len2+1):\n",
    "            dp[0][j] = j\n",
    "\n",
    "        for i in range(1, len1+1):\n",
    "            for j in range(1, len2+1):\n",
    "                if word1[i-1] == word2[j-1]:\n",
    "                    dp[i][j] = min(\n",
    "                        dp[i-1][j-1],\n",
    "                        dp[i-1][j] + 1,\n",
    "                        dp[i][j-1] + 1\n",
    "                    )\n",
    "                else:\n",
    "                    dp[i][j] = min(\n",
    "                        dp[i-1][j] + 1,\n",
    "                        dp[i][j-1] + 1\n",
    "                    )\n",
    "        print(dp)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        n1 = len(word1)\n",
    "        n2 = len(word2)\n",
    "        res = n1+n2\n",
    "        dp = [[0 for j in range(n2+1)]for i in range(n1+1)]\n",
    "\n",
    "        for i in range(n1+1):\n",
    "            dp[i][0] = i\n",
    "        for i in range(n2+1):\n",
    "            dp[0][i] = i\n",
    "        print(dp)\n",
    "        for i in range(1,n1+1):\n",
    "            for j in range(1,n2+1):\n",
    "                if word1[i-1]==word2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1\n",
    "        print(dp)\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        n = len(word1)\n",
    "        m = len(word2)\n",
    "        dp = [[i+j for j in range(m+1)]for i in range(n+1)]\n",
    "        # for i in range(n+1):\n",
    "            # for j in range(m+1):\n",
    "                # dp[i][j] = i+j\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,m+1):\n",
    "                if word1[i-1]==word2[j-1]:\n",
    "                    dp[i][j]=dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        len1, len2 = len(word1), len(word2)\n",
    "        dp = [[0] * len1 for i in range(len2)]\n",
    "        # 初始化\n",
    "        if word1[0] == word2[0]:\n",
    "            dp[0][0] = 0\n",
    "            found1, found2 = True, True\n",
    "        else:\n",
    "            dp[0][0] = 2\n",
    "            found1, found2 = False, False\n",
    "        for i in range(1, len1):\n",
    "            if word1[i] == word2[0] or found1:\n",
    "                dp[0][i] = i\n",
    "                found1 = True\n",
    "            else:\n",
    "                dp[0][i] = i+2\n",
    "\n",
    "        for j in range(1, len2):\n",
    "            if word1[0] == word2[j] or found2:\n",
    "                dp[j][0] = j\n",
    "                found2 = True\n",
    "            else:\n",
    "                dp[j][0] = j+2\n",
    "        print(dp)\n",
    "        \n",
    "        # 状态转移方程\n",
    "        for i in range(1, len1):\n",
    "            for j in range(1, len2):\n",
    "                if word1[i] == word2[j]:\n",
    "                    dp[j][i] = dp[j-1][i-1]\n",
    "                else:\n",
    "                    dp[j][i] = 1 + min(dp[j-1][i], dp[j][i-1])\n",
    "        print(dp)\n",
    "        return dp[len2-1][len1-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        # m, n = len(word1), len(word2)\n",
    "        # dp = [[0]*(n+1) for _ in range(m+1)]\n",
    "        # for i in range(1, m+1):\n",
    "        #     for j in range(1, n+1):\n",
    "        #         if word1[i-1] == word2[j-1]:\n",
    "        #             dp[i][j] = dp[i-1][j-1]+1\n",
    "        #         else:\n",
    "        #             dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n",
    "        # return m+n-dp[m][n]*2\n",
    "\n",
    "        m, n = len(word1), len(word2)\n",
    "        dp = [list(range(i, i+n+1)) for i in range(m+1)]\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if word1[i-1] == word2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j], dp[i][j-1])+1\n",
    "        return dp[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        m, n = len(word1), len(word2)\n",
    "        dp = [[i + j for i in range(n + 1)] for j in range(m + 1)]\n",
    "        dp[0][0] = 0\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if word1[i - 1] == word2[j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j - 1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        m, n = len(word1), len(word2)\n",
    "        dp = [[0 for i in range(n+1)] for j in range(m+1)]\n",
    "        for i in range(m+1):\n",
    "            for j in range(n+1):\n",
    "                dp[i][j] = i + j\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                if word1[i-1] == word2[j-1]:\n",
    "                    dp[i][j] = min(dp[i][j], dp[i-1][j-1])\n",
    "                # else:\n",
    "                #     if j == 1 or word1[i-1] == word2[j-2]:\n",
    "                #         dp[i][j] = min(dp[i][j], dp[i][j-1] + 1)\n",
    "                #     if i == 1 or word1[i-2] == word2[j-1]:\n",
    "                #         dp[i][j] = min(dp[i][j], dp[i-1][j] + 1)\n",
    "                dp[i][j] = min(dp[i][j],dp[i-1][j-1] + 2,dp[i][j-1]+1,dp[i-1][j]+1)\n",
    "        return dp[m][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        dp=[list(range(i,len(word1)+1+i)) for i in range(len(word2)+1)]\n",
    "        for i in range(1,len(word2)+1):\n",
    "            for j in range(1,len(word1)+1):\n",
    "                if word2[i-1]==word1[j-1]:\n",
    "                    dp[i][j]=dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j]=min(dp[i][j-1]+1,dp[i-1][j]+1)\n",
    "        return dp[-1][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        m = len(word1)\n",
    "        n = len(word2)\n",
    "        dp = [[m+n for _ in range(n+1)] for _ in range(m+1)]\n",
    "        for i in range(m+1):\n",
    "            dp[i][0] = i\n",
    "        for j in range(n+1):\n",
    "            dp[0][j] = j\n",
    "        dp[0][0] = 0\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if word1[i-1]==word2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j],dp[i][j-1])+1\n",
    "        return dp[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        dp=[[len(word1) for _ in range(len(word1)+1)] for _ in range(len(word2)+1)]\n",
    "        for i in range(len(word2)+1):\n",
    "            dp[i][0]=0\n",
    "        for j in range(len(word1)+1):\n",
    "            dp[0][j]=0\n",
    "        for i in range(1,len(word2)+1):\n",
    "            for j in range(1,len(word1)+1):\n",
    "                if word2[i-1]==word1[j-1]:\n",
    "                    dp[i][j]=dp[i-1][j-1]+1\n",
    "                else:\n",
    "                    dp[i][j]=max(dp[i-1][j],dp[i][j-1])\n",
    "        k=len(word1)+len(word2)-2*dp[-1][-1]\n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        m,n=len(word2)+1,len(word1)+1\n",
    "        dp=[[i+j for i in range(n)] for j in range(m)]\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                if word1[j-1]==word2[i-1]: dp[i][j]=dp[i-1][j-1]\n",
    "                else: dp[i][j]=min(dp[i-1][j-1]+2,dp[i-1][j]+1,dp[i][j-1]+1)\n",
    "        return dp[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        # dp[i][j]: 给定word1[0: i + 1]和word2[0: j + 1], 使得word1[0: i + 1]和word2[0: j + 1]相同所需的最小步数\n",
    "        # dp[i][j] = dp[i - 1][j - 1], word1[i] == word2[j]\n",
    "        #          = min([1 + dp[i][j - 1], 1 + dp[i - 1][j], 2 + dp[i - 1][j - 1]]), word1[i] != word2[j]\n",
    "        dp = [[2 + i + j for j in range(len(word2))] for i in range(len(word1))]\n",
    "        if word1[0] == word2[0]:\n",
    "            dp[0][0] = 0\n",
    "        ind = dp[0][0] == 0\n",
    "        for j in range(1, len(word2)):\n",
    "            if ind:\n",
    "                dp[0][j] = j\n",
    "            else:\n",
    "                if word2[j] == word1[0]:\n",
    "                    dp[0][j] = j\n",
    "                    ind = True\n",
    "                else:\n",
    "                    dp[0][j] = j + 2\n",
    "        ind = dp[0][0] == 0\n",
    "        for i in range(1, len(word1)):\n",
    "            if ind:\n",
    "                dp[i][0] = i \n",
    "            else:\n",
    "                if word1[i] == word2[0]:\n",
    "                    dp[i][0] = i \n",
    "                    ind = True \n",
    "                else:\n",
    "                    dp[i][0] = i + 2\n",
    "        for i in range(1, len(word1)):\n",
    "            for j in range(1, len(word2)):\n",
    "                if word1[i] == word2[j]:\n",
    "                    dp[i][j] = dp[i - 1][j - 1]\n",
    "                else:\n",
    "                    dp[i][j] = min([1 + dp[i][j - 1], 1 + dp[i - 1][j], 2 + dp[i - 1][j - 1]])\n",
    "        return dp[- 1][- 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        m, n = len(word1) + 1, len(word2) + 1\n",
    "        dp = [[i + j for j in range(n)] for i in range(m)]\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                if word1[i-1] == word2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i][j-1] + 1, dp[i-1][j] + 1)\n",
    "        return dp[m-1][n-1]\n",
    "\n",
    "\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        m, n = len(word1) + 1, len(word2) + 1\n",
    "        dp = [[i+j for j in range(n)] for i in range(m)]\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                if word1[i-1] == word2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1)\n",
    "        return dp[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        m, n = len(word1) + 1, len(word2) + 1\n",
    "        dp = [[i + j for j in range(n)] for i in range(m)]\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                if word1[i-1] == word2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i][j-1] + 1, dp[i-1][j] + 1)\n",
    "        return dp[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        dp = [[float(\"inf\") for _ in range(len(word2) + 1)][:] for _ in range(len(word1) + 1)]\n",
    "        for i in range(len(word1) + 1):\n",
    "            dp[i][0] = i\n",
    "        for i in range(len(word2) + 1):\n",
    "            dp[0][i] = i\n",
    "        \n",
    "        for i in range(1, len(word1) + 1):\n",
    "            for j in range(1, len(word2) + 1):\n",
    "                if word1[i -1] == word2[j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j - 1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1)\n",
    "        \n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        word1 = \"$\"+word1\n",
    "        word2 = \"$\"+word2\n",
    "        matrix = [[i == j for i in word1] for j in word2]\n",
    "        matrix2 = [[len(word1)+len(word2) for i in word1] for j in word2]\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if i == 0 and j == 0:\n",
    "                    matrix2[i][j] = 0\n",
    "                elif i == 0:\n",
    "                    matrix2[i][j] = matrix2[i][j-1]+1\n",
    "                elif j == 0:\n",
    "                    matrix2[i][j] = matrix2[i-1][j]+1\n",
    "                else:\n",
    "                    matrix2[i][j] = min(matrix2[i-1][j]+1, matrix2[i][j-1]+1)\n",
    "                    if matrix[i][j]:\n",
    "                        matrix2[i][j] = min(matrix2[i][j], matrix2[i-1][j-1])\n",
    "        return matrix2[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        m, n = len(word1), len(word2)\n",
    "        if m == 0 or n == 0:\n",
    "            return m or n\n",
    "        dp = [[m+n for _ in range(n+1)] for _ in range(m+1)]\n",
    "        for i in range(m+1):\n",
    "            dp[i][0] = i\n",
    "        for j in range(n+1):\n",
    "            dp[0][j] = j\n",
    "            \n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if word1[i-1] != word2[j-1]:\n",
    "                    dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + 1\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j-1], min(dp[i][j-1], dp[i-1][j])+1)\n",
    "        \n",
    "        return dp[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        n1, n2 = len(word1), len(word2)\n",
    "        # res = 100000\n",
    "        dp = [[float('inf') for _ in range(n2+1)] for _ in range(n1+1)]\n",
    "        dp[0][0] = 0\n",
    "\n",
    "        for i in range(1,n1+1):\n",
    "            dp[i][0] = i\n",
    "        for j in range(1,n2+1):\n",
    "            dp[0][j] = j\n",
    "\n",
    "        for i in range(1,n1+1):\n",
    "            for j in range(1,n2+1):\n",
    "                if word1[i-1] == word2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1\n",
    "        # print(dp)       \n",
    "        return dp[n1][n2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        n=len(word1)\n",
    "        m=len(word2)\n",
    "        #dp[i][j] 使得s1前i位和前j位相同的最小步数\n",
    "        dp=[[float('inf') for _ in range(m+1)] for _ in range(n+1)]\n",
    "        dp[0][0]=0\n",
    "        for i in range(1,m+1):\n",
    "            dp[0][i]=i#无元素，删除i个元素\n",
    "        for i in range(1,n+1):\n",
    "            dp[i][0]=i\n",
    "        ans=float('inf')\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,m+1):\n",
    "                if word1[i-1]==word2[j-1]:\n",
    "                    dp[i][j]=dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1\n",
    "        return dp[n][m]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        l1, l2 = len(word1), len(word2)\n",
    "        dp = [[float('inf') for _ in range(l2+1)]for _ in range(l1+1)]\n",
    "\n",
    "        for i in range(l1+1):\n",
    "            dp[i][0] = i\n",
    "        for j in range(l2+1):\n",
    "            dp[0][j] = j\n",
    "\n",
    "        for i in range(1,l1+1):\n",
    "            for j in range(1,l2+1):\n",
    "                if word1[i-1]==word2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+2)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 本题重点在于初始化dp数组\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        m=len(word1)+1\n",
    "        n=len(word2)+1\n",
    "        dp=[[i+j for i in range(n)] for j in range(m)]\n",
    "        print(dp)\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                if word1[i-1]==word2[j-1]:\n",
    "                    dp[i][j]=dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+2)\n",
    "        return dp[-1][-1]\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        dp = [[float('inf') for _ in range(len(word2) + 1)] for _ in range(len(word1) + 1)]\n",
    "        dp[0][0] = 0\n",
    "        for i in range(1, len(word1) + 1):\n",
    "            dp[i][0] = dp[i - 1][0] + 1\n",
    "        for j in range(1, len(word2) + 1):\n",
    "            dp[0][j] = dp[0][j - 1] + 1\n",
    "        for i in range(1, len(word1) + 1):\n",
    "            for j in range(1, len(word2) + 1):\n",
    "                if word1[i - 1] == word2[j - 1]: dp[i][j] = dp[i - 1][j - 1]\n",
    "                else:\n",
    "                    dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1])\n",
    "        print(dp)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        # dp[i+1][j] = dp[i][j]\n",
    "        dp = [ [(0,-1)],  ]\n",
    "        max_match = 0\n",
    "        max_match_len = 0\n",
    "        for w in word2:\n",
    "            match = []\n",
    "\n",
    "            # max_m_len = len(word1)\n",
    "            for d in dp[-1]:\n",
    "                a = word1.find(w, d[1]+1,) \n",
    "                if a>=0:\n",
    "                    match.append((d[0]+1, a))\n",
    "                match.append((d[0], d[1]))\n",
    "                if match!=[] and match[-1][0]>max_match:\n",
    "                    max_match =  match[-1][0]\n",
    "                    max_match_len = match[-1][1]\n",
    "            match.sort(key=lambda x:x[0]*len(word1)+x[1])\n",
    "            new_match = [match[0]]\n",
    "            for i in range(1, len(match)):\n",
    "                if match[i][0]!=match[i-1][0]:\n",
    "                    new_match.append(match[i])\n",
    "            dp.append(new_match)\n",
    "        print(dp)\n",
    "        match_num = max(list(zip(*dp[-1]))[0])\n",
    "        # print(dp)\n",
    "        return len(word1) + len(word2) - 2*match_num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        \"\"\"\n",
    "        dp[i][j] distance between word1[...i] and word2[...j]\n",
    "        if word1[i] == word2[j]:\n",
    "            dp[i][j] = dp[i - 1][j - 1]\n",
    "        else:\n",
    "            dp[i][j] = min(dp[i - 1][j - 1] + 1, dp[i][j - 1] + 1, dp[i - 1][j] + 1)       \n",
    "        \"\"\"\n",
    "        m = len(word1)\n",
    "        n = len(word2)\n",
    "        dp = [[float('inf') for j in range(n + 1)] for i in range(m + 1)]\n",
    "        dp[0][0] = 0\n",
    "        for i in range(m + 1):\n",
    "            for j in range(n + 1):\n",
    "                if i == 0 and j == 0:\n",
    "                    continue\n",
    "                if i == 0 or j == 0:\n",
    "                    dp[i][j] = abs(i - j)\n",
    "                    continue\n",
    "                if word1[i - 1] == word2[j - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j - 1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i - 1][j - 1] + 2, dp[i][j - 1] + 1, dp[i - 1][j] + 1)\n",
    "        print(dp)\n",
    "        return dp[m][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDistance(self, word1: str, word2: str) -> int:\n",
    "        m,n=len(word1),len(word2)\n",
    "        dp=[[float('inf') for i in range(n+1)] for i in range(m+1)]\n",
    "        for i in range(1,m+1):\n",
    "            dp[i][0]=i\n",
    "        for j in range(1,n+1):\n",
    "            dp[0][j]=j\n",
    "        dp[0][0]=0\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                if word1[i-1]==word2[j-1]:\n",
    "                    dp[i][j]=dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1\n",
    "        print(dp)\n",
    "        return dp[m][n]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
